/*
 * Copyright (c) 2003-2006 jMonkeyEngine
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *
 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 
 *   may be used to endorse or promote products derived from this software 
 *   without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package com.jmex.terrain.util;

import java.util.logging.Logger;

import com.jme.system.JmeException;

/**
 * <code>ParticleDepositionHeightMap</code> creates a heightmap based on the
 * Particle Deposition algorithm based on Jason Shankel's paper from
 * "Game Programming Gems". A heightmap is created using a Molecular beam
 * epitaxy, or MBE, for depositing thin layers of atoms on a substrate.
 * We drop a sequence of particles and simulate their flow across a surface
 * of previously dropped particles. This creates a few high peaks, for further
 * realism we can define a caldera. Similar to the way volcano's form
 * islands, rock is deposited via lava, when the lava cools, it recedes
 * into the volcano, creating the caldera.
 *
 * @author Mark Powell
 * @version $Id: ParticleDepositionHeightMap.java,v 1.4 2007/08/02 23:16:20 nca Exp $
 */
public class ParticleDepositionHeightMap extends AbstractHeightMap {
    private static final Logger logger = Logger
            .getLogger(ParticleDepositionHeightMap.class.getName());

	//Attributes.
	private int jumps;
	private int peakWalk;
	private int minParticles;
	private int maxParticles;
	private float caldera;

	/**
	 * Constructor sets the attributes of the Particle Deposition
	 * Height Map and then generates the map.
	 *
	 * @param size the size of the terrain where the area is size x size.
	 * @param jumps number of areas to drop particles. Can also think
	 * 		of it as the number of peaks.
	 * @param peakWalk determines how much to agitate the drop point
	 * 		during a creation of a single peak. The lower the number
	 * 		the more the drop point will be agitated. 1 will insure
	 * 		agitation every round.
	 * @param minParticles defines the minimum number of particles to
	 * 		drop during a single jump.
	 * @param maxParticles defines the maximum number of particles to
	 * 		drop during a single jump.
	 * @param caldera defines the altitude to invert a peak. This is
	 * 		represented as a percentage, where 0.0 will not invert
	 * 		anything, and 1.0 will invert all.
	 *
	 * @throws JmeException if any value is less than zero, and
	 * 		if caldera is not between 0 and 1. If minParticles is greater than
	 * 		max particles as well.
	 */
	public ParticleDepositionHeightMap(
		int size,
		int jumps,
		int peakWalk,
		int minParticles,
		int maxParticles,
		float caldera) {

		if (size <= 0
			|| jumps < 0
			|| peakWalk < 0
			|| minParticles > maxParticles
			|| minParticles < 0
			|| maxParticles < 0) {

			throw new JmeException(
				"values must be greater than zero, "
					+ "and minParticles must be greater than maxParticles");
		}
		if (caldera < 0.0f || caldera > 1.0f) {
			throw new JmeException(
				"Caldera level must be " + "between 0 and 1");
		}

		this.size = size;
		this.jumps = jumps;
		this.peakWalk = peakWalk;
		this.minParticles = minParticles;
		this.maxParticles = maxParticles;
		this.caldera = caldera;

		load();
	}

	/**
	 * <code>load</code> generates the heightfield using the Particle Deposition
	 * algorithm. <code>load</code> uses the latest attributes, so a call
	 * to <code>load</code> is recommended if attributes have changed using
	 * the set methods.
	 */
	public boolean load() {
		int x, y;
		int calderaX, calderaY;
		int sx, sy;
		int tx, ty;
		int m;
		float calderaStartPoint;
		float cutoff;
		int dx[] = { 0, 1, 0, size - 1, 1, 1, size - 1, size - 1 };
		int dy[] = { 1, 0, size - 1, 0, size - 1, 1, size - 1, 1 };
		float[][] tempBuffer = new float[size][size];
		//map 0 unmarked, unvisited, 1 marked, unvisited, 2 marked visited.
		int[][] calderaMap = new int[size][size];
		boolean done;

		int minx, maxx;
		int miny, maxy;

		if (null != heightData) {
			unloadHeightMap();
		}

		heightData = new int[size*size];

		//create peaks.
		for (int i = 0; i < jumps; i++) {

			//pick a random point.
			x = (int) (Math.rint(Math.random() * (size - 1)));
			y = (int) (Math.rint(Math.random() * (size - 1)));

			//set the caldera point.
			calderaX = x;
			calderaY = y;

			int numberParticles =
				(int) (Math
					.rint(
						(Math.random() * (maxParticles - minParticles))
							+ minParticles));
			//drop particles.
			for (int j = 0; j < numberParticles; j++) {
				//check to see if we should aggitate the drop point.
				if (peakWalk != 0 && j % peakWalk == 0) {
					m = (int) (Math.rint(Math.random() * 7));
					x = (x + dx[m] + size) % size;
					y = (y + dy[m] + size) % size;
				}

				//add the particle to the piont.
				tempBuffer[x][y] += 1;

				sx = x;
				sy = y;
				done = false;

				//cause the particle to "slide" down the slope and settle at
				//a low point.
				while (!done) {
					done = true;

					//check neighbors to see if we are higher.
					m = (int) (Math.rint((Math.random() * 8)));
					for (int jj = 0; jj < 8; jj++) {
						tx = (sx + dx[(jj + m) % 8]) % (size);
						ty = (sy + dy[(jj + m) % 8]) % (size);

						//move to the neighbor.
						if (tempBuffer[tx][ty] + 1.0f < tempBuffer[sx][sy]) {
							tempBuffer[tx][ty] += 1.0f;
							tempBuffer[sx][sy] -= 1.0f;
							sx = tx;
							sy = ty;
							done = false;
							break;
						}
					}
				}

				//This point is higher than the current caldera point,
				//so move the caldera here.
				if (tempBuffer[sx][sy] > tempBuffer[calderaX][calderaY]) {
					calderaX = sx;
					calderaY = sy;
				}
			}

			//apply the caldera.
			calderaStartPoint = tempBuffer[calderaX][calderaY];
			cutoff = calderaStartPoint * (1.0f - caldera);
			minx = calderaX;
			maxx = calderaX;
			miny = calderaY;
			maxy = calderaY;

			calderaMap[calderaX][calderaY] = 1;

			done = false;
			while (!done) {
				done = true;
				sx = minx;
				sy = miny;
				tx = maxx;
				ty = maxy;

				for (x = sx; x <= tx; x++) {
					for (y = sy; y <= ty; y++) {

						calderaX = (x + size) % size;
						calderaY = (y + size) % size;

						if (calderaMap[calderaX][calderaY] == 1) {
							calderaMap[calderaX][calderaY] = 2;

							if (tempBuffer[calderaX][calderaY] > cutoff
								&& tempBuffer[calderaX][calderaY]
									<= calderaStartPoint) {

								done = false;
								tempBuffer[calderaX][calderaY] =
									2 * cutoff - tempBuffer[calderaX][calderaY];

								//check the left and right neighbors
								calderaX = (calderaX + 1) % size;
								if (calderaMap[calderaX][calderaY] == 0) {
									if (x + 1 > maxx) {
										maxx = x + 1;
									}
									calderaMap[calderaX][calderaY] = 1;
								}

								calderaX = (calderaX + size - 2) % size;
								if (calderaMap[calderaX][calderaY] == 0) {
									if (x - 1 < minx)
										minx = x - 1;
									calderaMap[calderaX][calderaY] = 1;
								}

								//check the upper and lower neighbors.
								calderaX = (x + size) % size;
								calderaY = (calderaY + 1) % size;
								if (calderaMap[calderaX][calderaY] == 0) {
									if (y + 1 > maxy)
										maxy = y + 1;
									calderaMap[calderaX][calderaY] = 1;
								}
								calderaY = (calderaY + size - 2) % size;
								if (calderaMap[calderaX][calderaY] == 0) {
									if (y - 1 < miny)
										miny = y - 1;
									calderaMap[calderaX][calderaY] = 1;
								}
							}
						}
					}
				}
			}
		}

		erodeTerrain(tempBuffer);
		normalizeTerrain(tempBuffer);

		//transfer the new terrain into the height map.
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				setHeightAtPoint((int) tempBuffer[i][j], j, i);
			}
		}

		logger.info("Created heightmap using Particle Deposition");

		return false;
	}

	/**
	 * <code>setJumps</code> sets the number of jumps or peaks that will
	 * be created during the next call to <code>load</code>.
	 * @param jumps the number of jumps to use for next load.
	 * @throws JmeException if jumps is less than zero.
	 */
	public void setJumps(int jumps) {
		if (jumps < 0) {
			throw new JmeException("jumps must be positive");
		}
		this.jumps = jumps;
	}

	/**
	 * <code>setPeakWalk</code> sets how often the jump point will be
	 * aggitated. The lower the peakWalk, the more often the point will
	 * be aggitated.
	 *
	 * @param peakWalk the amount to aggitate the jump point.
	 * @throws JmeException if peakWalk is negative or zero.
	 */
	public void setPeakWalk(int peakWalk) {
		if (peakWalk <= 0) {
			throw new JmeException(
				"peakWalk must be greater than " + "zero");
		}
		this.peakWalk = peakWalk;
	}

	/**
	 * <code>setCaldera</code> sets the level at which a peak will be
	 * inverted.
	 *
	 * @param caldera the level at which a peak will be inverted. This must be
	 * 		between 0 and 1, as it is represented as a percentage.
	 * @throws JmeException if caldera is not between 0 and 1.
	 */
	public void setCaldera(float caldera) {
		if (caldera < 0.0f || caldera > 1.0f) {
			throw new JmeException(
				"Caldera level must be " + "between 0 and 1");
		}
		this.caldera = caldera;
	}

	/**
	 * <code>setMaxParticles</code> sets the maximum number of particles
	 * for a single jump.
	 * @param maxParticles the maximum number of particles for a single jump.
	 * @throws JmeException if maxParticles is negative or less than
	 * 		the current number of minParticles.
	 */
	public void setMaxParticles(int maxParticles) {
		this.maxParticles = maxParticles;
	}

	/**
	 * <code>setMinParticles</code> sets the minimum number of particles
	 * for a single jump.
	 * @param minParticles the minimum number of particles for a single jump.
	 * @throws JmeException if minParticles are greater than
	 * 		the current maxParticles;
	 */
	public void setMinParticles(int minParticles) {
		if (minParticles > maxParticles) {
			throw new JmeException(
				"minParticles must be less " + "than the current maxParticles");
		}
		this.minParticles = minParticles;
	}
}
